import java.util.Arrays;
import java.util.Random;

public class driver {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
	//	boolean success=true;
		//for (int i = 10000; i < 100001; i = i + 10000) {
		//	RBTree t = new RBTree();
		//	System.out.println("inserting " + i + " nodes");
		//	insertTree(i, t);
		//	
		//	if (!(t.size()<=i)){
		//		success=false;
		//	}
		//	
		//	System.out.println("size: " +t.size() + "\nsize <= "+ i + " : " + (t.size()<=i));
		//	System.out.println("max depth is " + t.maxDepth());
		//	System.out
		//			.println("max depth should be < = "
		//					+ 2*Math.log(t.size()+1) / Math.log(2)
		//					+ "\n"
		//					+ (t.maxDepth()<=2*Math.log(t.size()+1) / Math.log(2))
		//					+ "\n\n");
//
	//		if (!(t.maxDepth()<=2*Math.log(t.size()+1) / Math.log(2)))
		//		success=false;
			//}
		//System.out.println(success);
		
		printTable();
		}
	
	public static void printTable(){
		System.out.println("#insert"+'\t'+"size1"+'\t'+"maxDepth1" +'\t'+"size2"+'\t'+"maxDepth2"+'\t'+"size3"+'\t'+"maxDepth3"+'\t'+"size4"+'\t'+"maxDepth4"+'\t'+"average"+'\t'+"expected"+'\t'+"success");
		for (int i = 10000; i < 100001; i = i + 10000) {
			System.out.print(i+"\t");
			int[] maxDepth= new int[4];
			int[] size= new int[4];
			for (int j=0;j<4;j++){
				RBTree t=new RBTree();
				insertTree(i, t);
				maxDepth[j]=t.maxDepth();
				size[j]=t.size();
				System.out.print(Integer.toString(size[j])+"\t"+Integer.toString(maxDepth[j])+"\t");
			}
			double averageDepth=(maxDepth[0]+maxDepth[1]+maxDepth[2]+maxDepth[3])/4.0;
			double averageSize=(size[0]+size[1]+size[2]+size[3])/4.0;
			System.out.print(averageDepth+"\t"+2*Math.log(averageSize+1) / Math.log(2)+"\t");
			System.out.println(averageDepth<=2*Math.log(averageSize+1) / Math.log(2));
		}
	}
		

	

	private static void insertTree(int howMany, RBTree tree) {
		if(!tree.isValid()){System.out.print(false);}
		for (int i = 0; i < howMany; i++) {
			Random r = new Random();
			int key = r.nextInt();
			//System.out.println(key + "\t");
			
			tree.insert(key, Integer.toString(key));
		
		}
		if(!tree.isValid()){System.out.print(false);}
	}

	private static void randomInsertDeleate(int howMany, RBTree tree) {
		for (int i = 0; i < howMany; i++) {
			Random r = new Random();
			int key = r.nextInt();

			if (r.nextBoolean()) {
				System.out.print("insert:" + key + "\t");
				tree.insert(key, Integer.toString(key));
			} else {
				System.out.print("delete:" + key + "\t");
				tree.delete(key);
			}
		}
	}
}
